==========================
Operating System Internals
==========================

Process
=======
* A thread of execution

  * Program Counter
  * Register state
  * Local data, i.e. stack

* An address space

  * Could be a subset of a shared memory space 
  
    * MicroOS-II
    * Pre Windows CE 6.0 kernels   

  * Or virtual space
  
    * CE 6.0, NT (XP, Vista, 7), Linux

Simple System
=============
*Picture*

:: 

    +-Kernel----------------------------------+
    |                                         |
    |  +-Process-+  +-Process-+  +-Process-+  |
    |  |         |  |         |  |         |  |
    |  | Thread  |  | Thread  |  | Thread  |  |
    |  | Thread  |  |         |  |         |  |
    |  |         |  |         |  |         |  |
    |  +---------+  +---------+  +---------+  |
    |                                         |
    +-----------------------------------------+

Process and Thread Control APIs
===============================
* Create

  * Creation of the thread or task 
  
* Delete

  * Deletion of thread 
  
* Set Priorities

  * Set the priority of a thread

* Suspend/Resume

  * Suspend and resume the execution of a thread


Scheduling
==========
* One of the key features of an operating system is the scheduling of tasks or functions.
* Even systems without formal operating systems often use some form of simplistic scheduling.
* Non-OS approaches to scheduling.


Scheduler
=========
* The dispatcher component of OS 
* Schedules threads (tasks, processes) 
* Implements preemption 
* Implements scheduling algorithm(s) 
* Should be fast, efficient, deterministic

Scheduling algorithms 
=====================
* Priority scheduling algorithm

  * Highest priority runable task is the thread selected to execute

* Each thread is on one of two lists: 

  * Ready list
  * Wait or suspended list

Task States
===========

::

    PENDED    <----> READY/EXEC. <-----> DELAYED
      ^                 ^                   |
      |                 |                   |
      v                 v                   v
    PENDED &  -----> SUSPENDED   <------ DELAYED & 
    SUSPENDED                            SUSPENDED



Round Robin Scheduling
======================
* Each runable task executes for a quantum of time.
* After the quantum expires the next thread begins (continues) executing.
* Sometimes referred to as time-sharing or time-slicing.

Dynamic Priority Scheduling
===========================
* The priority of a given thread is based on dynamic conditions.
* NT/XP/Vista

  * NT gives a normal priority thread a boost after it is restarted from an I/O suspend.
  * NT gives the foreground task on the GUI a priority boost.

* Multimedia
  
  * Earliest deadline algorithm

Real-time scheduling algorithms
===============================
* Priority scheduling 
* Typical of Embedded and RTOS systems 
* May add round-robin for equal priority tasks

Rate Monotonic Scheduling
=========================
* Highest rate periodic event == highest priority
* The higher the rate of a periodic task the higher its priority.

  * For example, if task A executes once every 50 msec and task B executes once every 100 msec, then task A will receive a higher priority than task B.
  
* Provably correct

  * This approach has been proven to be optimal (Liu and Layland)
  
* Unfortunately for Embedded developers, many of the tasks that we have to deal with are not periodic in nature.

Earliest deadline first
=======================
* With this algorithm the scheduler is looking at the time when a task must be complete.
* It then schedules the task that has the earliest deadline approaching.
* This algorithm has been used in real-time multimedia systems.

  * You could think of a set of tasks where one is decoding frames of video and the other decoding frames of audio.
  
* The task that has the earliest need to deliver their frame is the thread that is executed.

Least Laxity
============
* Thread with least laxity is executed
* Laxity is the amount of time a thread has to spare before its task must be completed.

  * If a thread has 10 msec of work to perform and must deliver the result in 300 msec then it has 290 msec of laxity.
  * The algorithm chooses the task with the least laxity to execute.


Simple Round-Robin
==================
* Cooperative tasks 
* No interrupts 
* No priorities

.. code-block:: c

    PTASK pFunc[MAX_TASK];               // ptr to routine to run
    UCHAR currentTask = -1;              // initialize list of tasks to run
    pFunc[0] = MyFirstTask;
    pFunc[1] = My2ndTask;
    pFunc[2] = ...
    
    while(TRUE) {                        // forever loop
      if (++currentTask >= MAX_TASK) {
        currentTask = 0;
      }	
      
      if (pFunc[currentTask] != NULL) {  // call the next task
         pFunc[currentTask]();
      }
    }


Simple Round-Robin with Interrupts
==================================

*Background*

.. code-block:: c

    
    PTASK pFunc[MAX_TASK];                // ptr to routine to run 
    
    while(TRUE) {    // forever 
        if (++currentTask >= MAX_TASK) { 
            currentTask = 0;
        }
        
        if (pFunc[currentTask] != NULL) { // call the next task
            pFunc[currentTask]();
        }
    }

*Foreground*

.. code-block:: c

    PISR IDT[MAX_ISR];
    
    InterruptA() { 
        ...
    } 
    
    InterruptB() {
        ...
    }


With Function Queue Scheduling
==============================

*Background*

.. code-block:: c

    struct { PFUNC pFunc;                // function to run 
        PTASK pNext;                     // ptr to next task
    } TASK, *PTASK; 
    
    PTASK pHead = NULL;                  // start list 
    PTASK pNext = NULL;                  // next task 
    
    while(TRUE) {                        // forever
        if (pNext == NULL) 
            pNext = pHead;               // call the next task 
        if (pNext != NULL) {
            pNext->pFunc();
            pNext = pNext->pNext 
        }
    }

*Foreground*

.. code-block:: c

    PISR IDT[MAX_ISR]; 
    InterruptA() {
        ... 
        AddTask(pMytask)
    } 
    InterruptB() {
        ...
    }
    AddTask(PTASK pFunc) {
        // walk list from head insert pFunc at position in list depending on priority
    }